#include "KMP.h"

void MakeNext(std::string p, int next[])
{
	int j = 0;
	int k = -1;
	next[0] = -1;

	while (j < p.length() - 1)
	{
		if (k == -1 || p[j] == p[k])
		{
			j++;
			k++;
			next[j] = k;
		}
		else
		{
			k = next[k];
		}
	}
}

int KMP(std::string s, std::string p)
{
	int* next = new int[p.length()];
	if (nullptr == next)
	{
		return -1;
	}

	MakeNext(p, next);

	int i = 0;
	int j = 0;
	while (i < (int)s.length() && j < (int)p.length())
	{
		if (j == -1 || s[i] == p[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j >= (int)p.length())
	{
		return i - p.length();
	}
	else
	{
		return -1;
	}

	return 0;
}
